package BinaryTree.Medium;

import Structures.TreeNode;

import java.util.Stack;

public class LC1448 {
    public int goodNodes(TreeNode root) {
        if (root == null) return 0;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> maxNumberStack = new Stack<>();
        nodeStack.push(root);
        maxNumberStack.push(Integer.MIN_VALUE);

        int nGoodNodes = 0;
        while (!nodeStack.empty()) {
            TreeNode node = nodeStack.pop();
            int maxNumberOnRoute = maxNumberStack.pop();
            if (node.val >= maxNumberOnRoute) {
                nGoodNodes++;
                maxNumberOnRoute = node.val;
            }
            if (node.right != null) {
                nodeStack.push(node.right);
                maxNumberStack.push(maxNumberOnRoute);
            }
            if (node.left != null) {
                nodeStack.push(node.left);
                maxNumberStack.push(maxNumberOnRoute);
            }
        }

        return nGoodNodes;
    }
}
